class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []


class Solution(object):
    def cloneTree(self, root):
        d = {}
        if not root:
            return None
        def dfs(node):
            if node in d:
                new_node = d[node]
            else:
                new_node = Node(node.val)
                d[node] = new_node
            for child in node.children:
                new_node.children.append(dfs(child))
            return new_node

        return dfs(root)
